//K个一组翻转链表
class Solution {
public:
    //head->1->2->3->4->5->NULL , k = 2
    //记录head节点，记录2节点，记录4节点，5节点不逆序
    int k;
    ListNode* RerverseList(ListNode* head)
    {
        //头插法逆序
        ListNode* ret = head->next;
        ListNode* newhead = new ListNode;
        ListNode* cur = head->next;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }
        head->next = newhead->next;
        delete newhead;
        return ret;
        
    }
    ListNode* reverseKGroup(ListNode* head, int _k) {
        k = _k;
        int n = 0;
        ListNode* newhead = new ListNode;
        newhead->next = head;
        ListNode* start = newhead;//记录节点
        ListNode* cur = head;
        while(cur)
        {
            ++n;
            if(n % k == 0)
            {
                //该翻转了
                ListNode* next = cur->next;
                cur->next = nullptr;
                start = RerverseList(start); //Rerverse需要返回翻转后的尾节点方便连接
                start->next = next;
                cur = next;
            }
            else 
            {
                cur = cur->next;
            }
        }
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;

    }
};

//合并K个升序链表
class Solution {
public:
    vector<bool> check;
    class Compare
    {
        public:
        bool operator()(ListNode* l1,ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 1) return lists[0];
        if(lists.size() == 0) return nullptr;
        //记录一下最小的那个链表节点的数组下标
        //记录一下链表的个数，方便后续统计空节点
        check.resize(lists.size());

        int n = lists.size();
        ListNode* head = new ListNode;
        ListNode* cur = head;
        head->next = nullptr;
        //先把所有节点插入优先级队列
        priority_queue<ListNode*,vector<ListNode*>,Compare> pq;
        for(size_t i = 0 ; i < lists.size() ; ++i)
        {
            if(lists[i] != nullptr)
            {
                pq.push(lists[i]);
                lists[i] = lists[i]->next;
            }
        }
        while(true)
        {
            //找出所有链表的最小节点 √
            if(pq.empty()) break;
            ListNode* min = pq.top();
            ListNode* next = min->next;
            cur->next = min;
            min->next = nullptr;
            cur = min;
            pq.pop();
            if(next) pq.push(next);
        }
        ListNode* ret = head->next;
        delete head;
        return ret;

    }
};